//给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和。 
//
// 
//
// 示例 1： 
//
// 
//输入：a = 1, b = 2
//输出：3
// 
//
// 示例 2： 
//
// 
//输入：a = 2, b = 3
//输出：5
// 
//
// 
//
// 提示： 
//
// 
// -1000 <= a, b <= 1000 
// 
// Related Topics 位运算 数学 
// 👍 552 👎 0

package com.cute.leetcode.editor.cn;
public class SumOfTwoIntegers {
    public static void main(String[] args) {
        Solution solution = new SumOfTwoIntegers().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    class Solution {
        /**
         * 不使用+-运算符实现两个整数求和，整数可能为负数
         * 1.朴素算法，一位一位的进行比较，需要保留一个进位标志t，对当前两个数的第i位进行判断
         * 2.a^b代表的是没有进位的求和， (a&b)<<1 则代表了进位  最终(a&b)<<1会全为0
         */
        public int getSum(int a, int b) {
            //题解2的方法
            // return b == 0 ? a : getSum(a^b,(a&b)<<1);

            int ans = 0;
            for (int i = 0,t=0; i <32 ; i++) {
                //得到两个数当前位的值，进位标志初始为1
                int n1 = (a>>i)&1;
                int n2 = (b>>i)&1;

                if (n1 == n2 && n1 == 0){
                    //当前两个数都为0，只关心进位标志位，按照进位标志进行赋值，赋值后清空进位标志
                    ans |= t<<i;
                    t=0;
                }else if (n1 != n2 ){
                    //此时说明只有一位是1，将进位标志与1异或，标志位本身不发生变化，因为原来是1的话本位就应该是0，标志位仍为1
                    ans |= (t^1)<<i;
                }else {
                    //此时说明肯定会进位，当前为就看标志位了，而且标志位之后仍需赋值为1
                    ans |= t<<i;
                    t = 1;
                }
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}